#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <iostream>

namespace wb
{
template <typename Iter, typename Comp>
void sort(Iter first, Iter last, Comp cmp)
{
    if (first == last)
        return;
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    Iter midl = std::partition(first,
                               last,
                               [&pivot](const auto& x) { return x < pivot; });
    Iter midr =
        std::partition(midl,
                       last,
                       [&pivot](const auto& x) { return !(pivot < x); });
    sort(first, midl);
    sort(midr, last);
}

template <typename Iter>
void quickSort(Iter first, Iter last)
{
    static_assert(
        std::is_same_v<typename std::iterator_traits<Iter>::iterator_category,
                       std::random_access_iterator_tag>);
    sort(first, last);
}
}  // end of namespace wb

int main(int argc, const char** argv)
{
    std::vector<int> arr{1, 9, 8, 5, 0, 4, 2, 7};
    wb::quickSort(arr.begin(), arr.end());
    std::for_each(arr.begin(),
                  arr.end(),
                  [](auto& x) { std::cout << x << " "; });
    std::cout << std::endl;
    return 0;
}